Computation outsourcing has emerged as a common practice for enterprises and individuals, especially in the cloud setting. For example, an owner of a data set, often referred to as the source, wants to answer queries over the data set issued by one or more clients or users and, for reasons of scalability and efficiency, chooses to do so by employing a possibly untrusted server on the cloud.
An immediate by-product of outsourcing of data and computation, however, is the need for verification of the correctness of a computation. Such integrity protection is a core security goal in cloud computing. Ensuring that data contents remain intact in the lifetime of an outsourced data set and that query processing is handled correctly, producing accurate and up-to-date answers, lies at the foundation of secure cloud services.
Authenticated data structures provide cryptographically hardened integrity guarantees in distributed or cloud-based data management settings. They support authenticated queries on a data set that is outsourced to a third party and generally to an untrusted server, by allowing the server to return, along with the answer to a query, a proof that can validate the correct query execution. As such, authenticated queries find numerous applications in cloud-computing settings, where clients wish to verify the query results they receive from untrusted cloud machines.
For example, queries on the outsourced data may comprise pattern matching computations over a text to determine whether there are any patterns present in the text. In addition, queries on the outsourced data may comprise exact path queries over semi-structured data (such as XML documents).
A need exists for authenticated pattern matching and authenticated exact path queries.